/*
 * @lc app=leetcode.cn id=23 lang=golang
 *
 * [23] 合并K个排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	//归并
	l := len(lists)
	if l == 0 {
		return nil
	} else if l == 1 {
		return lists[0]
	} else if l == 2 {
		return mergeTwoLists(lists[0], lists[1])
	} else {
		m := l / 2
		left := mergeKLists(lists[:m])
		right := mergeKLists(lists[m:])

		return mergeTwoLists(left, right)
	}
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	} else {
		if l1.Val < l2.Val {
			l1.Next = mergeTwoLists(l1.Next, l2)
			return l1
		} else {
			l2.Next = mergeTwoLists(l1, l2.Next)
			return l2
		}
	}
}

// @lc code=end

